import java.util.ArrayDeque;
import java.util.ArrayList;

/*
题目描述：滑动窗口的最大值  O(n)
方法：
用一个双端队列存储index，队列头维护当前窗口最大值的下标
 */
public class E59 {
    public static void main(String[] args) {
        int[] array = {2,3,4,2,6,2,5,1};
        int size = 3;
        ArrayList<Integer> res = maxInWindows(array, size);
        System.out.println(res);
    }

    public static ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> res = new ArrayList<>();
        if(num == null || size <= 0 || num.length < size){
            return res;
        }
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < num.length; i++){
            while(!deque.isEmpty() && num[deque.peekLast()] < num[i]){
                deque.pollLast();
            }
            deque.offerLast(i);
            //判断首元素是否过期
            if(deque.peekFirst() == i - size){
                deque.pollFirst();
            }
            if(i >= size - 1){
                res.add(num[deque.peekFirst()]);
            }
        }
        return res;
    }
}
/*
[4, 4, 6, 6, 6, 5]
 */